package lk;

import java.util.*;

public class D230923 {
    // 确定两个字符串是否接近
    // 1. 可以任意交换字符的位置
    // 2. 可以将 'a' 全部变为 'b'，'b' 全部变为 'a'，前提是字符串有 'a' 和 'b'
    // 如果进行上述任意次操作，两个字符串可以相等，就说明字符串接近
    // 思路：哈希表统计字符串中各个字符出现的次数
    // 比较字符种类是否相同（字符串1有 'a' 和 'b'，字符串2也必须有 'a' 和 'b'）
    // 比较次数是否相同

    // 时间：O(n + m)
    // 空间：O(1)
    // 使用了常数大小的数组，对常数大小的数组进行了排序
    public boolean closeStrings(String s1, String s2) {
        // 统计两个字符串中, 各个字符出现的次数
        int[] c1 = new int[26], c2 = new int[26];
        for (char c : s1.toCharArray()) c1[c - 'a']++;
        for (char c : s2.toCharArray()) c2[c - 'a']++;
        // 遍历统计数组, 查看两个数组中, 字符的种类是否相同（数组1中有 a，数组2中也必须有 a）
        for (int i = 0; i < 26; i++) {
            if (c1[i] + c2[i] == 0) continue;
            if (c1[i] == 0 || c2[i] == 0) return false;
        }
        // 排序统计数组
        Arrays.sort(c1); Arrays.sort(c2);
        // 遍历统计数组，不在乎是什么字符，看次数是否相同
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }


    // 相等行列对
    // 一个 n x n 的数组，如果有 一行 与 一列 元素相等，就是相等行列对，返回相等行列对的数目
    // 1. 嵌套循环，每一行 与 每一列 进行比较
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count++;
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] != grid[k][j]) {
                        count--;
                        break;
                    }
                }
            }
        }
        return count;
    }

    // 2. 使用哈希表统计
    public int equalPairs2(int[][] grid) {
        int n = grid.length;
        Map<List<Integer>, Integer> map = new HashMap<>();

        // 遍历数组的每一行，将每一行作为 key 放入 map 中，统计次数
        for (int[] row : grid) {
            List<Integer> arr = new ArrayList<>();
            for (int num : row) {
                arr.add(num);
            }
            map.put(arr, map.getOrDefault(arr, 0) + 1);
        }

        int res = 0;
        // 遍历数组的每一列，通过哈希表中的记录，查看是否有相等的行
        for (int j = 0; j < n; j++) {
            List<Integer> arr = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                arr.add(grid[i][j]);
            }
            if (map.containsKey(arr)) {
                res += map.get(arr);
            }
        }
        return res;
    }

}
